LeetCode 235、二叉搜索树的最近公共祖先

一、题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉搜索树的最近公共祖先（ LeetCode 235 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // 二叉搜索树的特点是，对于每一个节点 root 来说
        // root.left < root < root.right

        // 如果说 root 是 p、q 的最近公共祖先，也就意味值 p、q 在 root 的两侧
        // 假设 p 在 root 的左侧，q 在 root 的右侧
        // 那么 p.val < root.val < q.val
        // 1、root.val - p.val > 0
        // 2、root.val - q.val < 0
        // 即 ( root.val - p.val ) * ( root.val - q.val ) < 0
        // 所以，如果发现 ( root.val - p.val ) * ( root.val - q.val ) > 0 
        // 说明 p、q 在 root 的同一侧，不是最近公共祖先
        // 需要搜索 root 的左右子树

        // 由于所有节点的值都是唯一的，当出现 ( root.val - p.val ) * ( root.val - q.val ) = 0 时
        // 说明 p、q 中有一个节点是 root 节点，即 p 是 q 的祖先节点，或者 q 是 p 的祖先节点
        while (（long) (root.val - p.val) * (root.val - q.val) > 0 ){

            // 当进入到这个循环的时候，说明 p、q 在 root 的同一侧

            // 如果 p.val < root.val，也说明 q.val < root.val，因为只有这样，乘积才能大于 0
            if( p.val < root.val ){

                // 接下来往左子树寻找
                root = root.left;

            // 如果 p.val > root.val，也说明 q.val > root.val，因为只有这样，乘积才能大于 0
            }else{

                // 接下来往右子树寻找
                root = root.right;
            }
        }

        // 跳出循环，说明 (root.val - p.val) * (root.val - q.val) <= 0 
        // 此时，root 就是 p 、q 的最近公共祖先节点
        return root;
    }

}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉搜索树的最近公共祖先（ LeetCode 235 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        // 二叉搜索树的特点是，对于每一个节点 root 来说
        // root->left < root < root->right

        // 如果说 root 是 p、q 的最近公共祖先，也就意味值 p、q 在 root 的两侧
        // 假设 p 在 root 的左侧，q 在 root 的右侧
        // 那么 p->val < root->val < q->val
        // 1、root->val - p->val > 0
        // 2、root->val - q->val < 0
        // 即 ( root->val - p->val ) * ( root->val - q->val ) < 0
        // 所以，如果发现 ( root->val - p->val ) * ( root->val - q->val ) > 0 
        // 说明 p、q 在 root 的同一侧，不是最近公共祖先
        // 需要搜索 root 的左右子树

        // 由于所有节点的值都是唯一的，当出现 ( root->val - p->val ) * ( root->val - q->val ) = 0 时
        // 说明 p、q 中有一个节点是 root 节点，即 p 是 q 的祖先节点，或者 q 是 p 的祖先节点
        while ( (root->val - p->val) * (root->val - q->val) > 0 ){

            // 当进入到这个循环的时候，说明 p、q 在 root 的同一侧

            // 如果 p->val < root->val，也说明 q->val < root->val，因为只有这样，乘积才能大于 0
            if( p->val < root->val ){

                // 接下来往左子树寻找
                root = root->left;

            // 如果 p->val > root->val，也说明 q->val > root->val，因为只有这样，乘积才能大于 0
            }else{

                // 接下来往右子树寻找
                root = root->right;
            }
        }

        // 跳出循环，说明 (root->val - p->val) * (root->val - q->val) <= 0 
        // 此时，root 就是 p 、q 的最近公共祖先节点
        return root;
    }

};

3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉搜索树的最近公共祖先（ LeetCode 235 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        # 二叉搜索树的特点是，对于每一个节点 root 来说
        # root.left < root < root.right

        # 如果说 root 是 p、q 的最近公共祖先，也就意味值 p、q 在 root 的两侧
        # 假设 p 在 root 的左侧，q 在 root 的右侧
        # 那么 p.val < root.val < q.val
        # 1、root.val - p.val > 0
        # 2、root.val - q.val < 0
        # 即 ( root.val - p.val ) * ( root.val - q.val ) < 0
        # 所以，如果发现 ( root.val - p.val ) * ( root.val - q.val ) > 0 
        # 说明 p、q 在 root 的同一侧，不是最近公共祖先
        # 需要搜索 root 的左右子树

        # 由于所有节点的值都是唯一的，当出现 ( root.val - p.val ) * ( root.val - q.val ) = 0 时
        # 说明 p、q 中有一个节点是 root 节点，即 p 是 q 的祖先节点，或者 q 是 p 的祖先节点
        while (root.val - p.val) * (root.val - q.val) > 0 :

            # 当进入到这个循环的时候，说明 p、q 在 root 的同一侧

            # 如果 p.val < root.val，也说明 q.val < root.val，因为只有这样，乘积才能大于 0
            if p.val < root.val :

                # 接下来往左子树寻找
                root = root.left

            # 如果 p.val > root.val，也说明 q.val > root.val，因为只有这样，乘积才能大于 0
            else:

                # 接下来往右子树寻找
                root = root.right


        # 跳出循环，说明 (root.val - p.val) * (root.val - q.val) <= 0 
        # 此时，root 就是 p 、q 的最近公共祖先节点
        return root